% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode

% This is a simple template for a LaTeX document using the "article" class.
% See "book", "report", "letter" for other types of document.

\documentclass[runningheads,a4paper]{llncs} % use larger type; default would be 10pt
%\usepackage{llncsdoc}

\titlerunning{ }
\authorrunning{ }

\usepackage[UTF8]{inputenc} % set input encoding (not needed with XeLaTeX)
\usepackage{aeguill}
%%% Examples of Article customizations
% These packages are optional, depending whether you want the features they provide.
% See the LaTeX Companion or other references for full information.

%%% PAGE DIMENSIONS
%\usepackage{geometry} % to change the page dimensions
%\geometry{a4paper} % or letterpaper (US) or a5paper or....
% \geometry{margins=2in} % for example, change the margins to 2 inches all round
% \geometry{landscape} % set up the page for landscape
%   read geometry.pdf for detailed page layout information

\usepackage{graphicx} % support the \includegraphics command and options

%\usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent

%%% PACKAGES
%\usepackage{booktabs} % for much better looking tables
%\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{subfig} % make it possible to include more than one captioned figure/table in a single float
% These packages are all incorporated in the memoir class to one degree or another...

%%% HEADERS & FOOTERS
%\usepackage{fancyhdr} % This should be set AFTER setting up the page geometry
%\pagestyle{fancy} % options: empty , plain , fancy
%\renewcommand{\headrulewidth}{0pt} % customise the layout...
%\lhead{SMDP-F2013 group 3}\chead{Feature to code mapping}\rhead{ITU}
%\lfoot{}\cfoot{\thepage}\rfoot{}

%%% SECTION TITLE APPEARANCE
%\usepackage{sectsty}
%\allsectionsfont{\sffamily\mdseries\upshape} % (See the fntguide.pdf for font help)
% (This matches ConTeXt defaults)

\usepackage{hyperref}
\usepackage{listings}
\lstset{
  basicstyle=\ttfamily,
  columns=flexible
}

%%% ToC (table of contents) APPEARANCE
%\usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
%\usepackage[titles,subfigure]{tocloft} % Alter the style of the Table of Contents
%\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
%\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!

%%% END Article customizations

%%% The "real" document content comes below...

\title{SMDP-F2013 \\Feature to code mapping}
\author{Svolka Viktoras, Siyan Stoychev Panayotov, Christian Lyngbye}
\institute{ITU, Rued Langgaards Vej 7, 2300 København}
%\date{} % Activate to display a given date or no date (if empty),
         % otherwise the current date is printed 

\begin{document}
\maketitle
\begin{abstract}
Feature variability is common to many embedded software projects that are designed to be as small as possible because there is a natural limit on the available space for software on embedded systems. 
Variability is mapped to artifacts like source code files and this makes it possible to create different products from the same core project. 
We investigate the feasibility of designing a textual Domain Specific Language (DSL) that can be used to specify the mapping of pre-defined features to code. 

We hope to improve traceability and simplify the modification of the build systems when adding/removing features with mappings, by designing an external DSL.
  
By developing a prototype of a text editor for our DSL along with a template which we can use to generate a partial makefile to replace the mapping in makefiles in an embedded software project, we discover that it is feasible to design a DSL that separates the mapping of features to code from build tool artifacts.
The project repository is publicly available https://code.google.com/p/mdd-feature-code/
\end{abstract}
%We do a case study by prototyping and succeed in building a DSL which we use to extract and generate a makefile for one project.
\section{Introduction}
Modeling can be used to gain abstraction in certain technical domains where reading and editing complex code or scripts is necessary for the maintenance of software. By introducing a Domain Specific Language(DSL) it might allow domain experts without technical backgrounds to extend or maintain software in cooperation with software engineers.
However our domain is full  of stakeholders with technical backgrounds who we presume know the domain well.

Embedded software incorporates variability by only including the features that are needed in order to adopt a program to a specific piece of hardware. This variability is often determined at build time by the configuration manager or developer who builds the program. The build system needs to keep track of the variability of features and how the features map to the source code in the project. 

Some software projects combine the mapping of variability with the compilation details into build files that can be run by pre-defined automated build systems. 
It can be a time consuming task for a developer to manually create and maintain this build/make systems especially when adding new features to projects of variable nature. It might save time for developers or configuration mappers if the mapping of features to code was separated from the verbose technical details of a makefile. 
Another issue that can arise with variability is that over the lifetime of a project the features might get deprecated or impossible to select (zombie feature \cite{Tartler-2009-Zombie}). Due to this gradual decay of software projects it could be useful to accumulate mappings between features and artifacts into one place in order to maintain consistency in the mapping between features and artifacts.

By proving that it is feasible to design a language that can express the mapping of variability in build systems we wish to make it easier to maintain traceability of mapping from features to code in existing embedded software projects for developers and configuration managers. This could encourage the reengineering of existing projects in order to separate the mapping of features to code from build system details which might increase the long term viability of software projects.

In order to understand the domain we will investigate the use of variability of a few existing open source projects that use makefiles as build tools while having a feature configuration modeled.  Depending on the mappings which we can find, we will try to build a prototype that will be useful for the cases we decide on supporting.
The model driven development framework EMF\footnote{Eclipse Modeling Framework} can help with designing an external DSL from a graphical metamodel and generating a textual editor with modern features like syntax highlighting and auto completion. We use it to design and implement our technical solution which is an Eclipse plugin, that supports our concrete syntax, and a generator that can translate instances of our model into text files that support the Makefile syntax.


We start by describing the technologies of the domain in section\ref{sec:back}. Afterwards we analyze the mappings in open source projects in section \ref{sec:ana} where we establish a foundation of understanding to use to design our abstract metamodel. We describe the technical solution in section \ref{sec:tech} by providing examples to give an insight into which challenges we faced during the construction of our DSL.  We evaluate our solution in section \ref{sec:eval} by addressing whether or not we succeeded in reaching our goals and what we could have improved. In order to address the validity of our work we address the threats in section \ref{sec:threats}. %Following this we provide threats to the validity of our evaluation and discussion of our results. 
Next to last is a description of similar work or research in section \ref{sec:related}. Finally we provide a conclusion in section \ref{sec:conc}.

During the first part of the course one project member disbanded the group. As a result of this we couldn’t accomplish as much as we would have hoped, and we cut down the evaluation section.
\section{Background \label{sec:back}}
The variability of a Software Product Line (SPL) is designed to be configurable by a developer using \textbf{D}ecision \textbf{M}odeling, \textbf{F}eature \textbf{M}odeling  \cite{Czarnecki-2012-Comparison} or a combination. FM approaches are directly derived from the work on Feature-Oriented Domain Analysis (FODA)\cite{kang1990feature}. FODA is an established domain of research in which the focus is describing the variability using feature models. 

Software projects written using the C-family programming language can be built using different tools and compilers. All tasks required to compile such a project can be automated using a build tool. Build tools automate the process of compiling, packaging and deploying the final product. 

GNU Make\footnote{http://www.gnu.org/software/make/} is a software tool used to build software projects or just execute commands by running the text files called Makefiles. They are written in a declarative syntax and contain three basic elements - output files, referred to as targets, a list of input files, called dependencies, and the instructions how to process them, declared as rules. 

Makefiles allow us to conditionally modify the list of dependencies of each target according to the selected build options. The inclusion of a dependency can be represented as a Boolean expression of the build options, called presence condition (PC). If the presence condition is evaluated to false, the dependency is removed, else it is included.


The variability of embedded systems is realized in three ways\cite{Dietrich-2012-Extraction} :
\begin{description}
\item[Intended variability] Feature/Decision modeling providing choices of which features to include.
\item[Coarse-grained variability] The build system decides which objects to include based on the intended variability.
\item[Fine-grained variability] The source code files included by the coarse-grained variability can encapsulate internal code in presence conditions that is included if the PC is true.
\end{description}

KConfig implements intended variability in the Linux kernel \footnote{http://www.kernel.org}. It defines a DSL that provides the means to define features in a way that resembles feature modeling. A developer can select features before compiling a project using a graphical user interface called menuconfig that creates a configuration of features in a file with the extension \texttt{.config}. Afterwards the make software can evaluate the configuration and proceed with different operations based on the features selected.

%The Kconfig DSL has a basic syntax with different kinds of types e.g booleans, strings. 
%It has basic syntax that allows you to add configuration options of various types, create dependencies and write description. 
%The utilities know how to read and parse the configuration files and create project configuration files (.config for Makefiles and autoconf.h for source files). 

Features are modeled with dependencies and a makefile will check the values of these variable features when compiling. 

There are different ways to implement coarse-grained variability in a Makefile:
\begin{description}
\item[KBuild] is used by Linux kernel and provides specialized Makefile syntax 
\begin{verbatim}romstage-$(CONFIG_HAVE_ACPI_RESUME) += cbmem.c\end{verbatim}
\item[Condition clauses]
	(\texttt{ifeq, ifneq, ifdef, ifndef}) are simple control flow conditions
\begin{verbatim}ifeq ($(CONFIG_DYNAMIC_CBMEM),y)...endif\end{verbatim}
% additional source files, by defining the conditions on some criterias.
\end{description}

%- extend the makefile syntax - targets, depenencies - what we will be using in the file we generate

KBuild is the infrastructure that manages the building of the Linux kernel image and its modules. It consists of Kconfig and Makefiles as seen in Fig. \ref{fig:buildsystemworkflow}. The Makefiles describe the commands needed to produce the kernel image and modules.

KBuild modules consist of one or many objects. These objects can either be compiled into built-in kernel modules, or compiled as dynamically loadable modules. Thus the KBuild Makefile syntax allows for two separate lists of objects: obj-y and obj-m, respectively. Configuration options are directly used in KBuild Makefiles as variables. Their values are loaded by the makefile, which reads  the .config file generated after configuring the kernel. Configuration variables are used in an expression:
\begin{verbatim}
obj-$(CONFIG_SOUND_VMIDI)+= v_midi.o
\end{verbatim}

\texttt{SOUND\_VMIDI} (MIDI device support) is defined in Kconfig as a tristate configuration option and thus \texttt{\$(CONFIG\_SOUND\_VMIDI)} evaluates to  \texttt{n} (disabled), \texttt{y} (for built-in) and \texttt{m}(for module). 

In KBuild it is also possible to map entire directories to a presence condition using a technique called loose coupling \cite{Dietrich-2012-Extraction} and the compiler conditionally descends into subdirectories and includes the source files in them. 
\begin{figure}[h!]
\centering
\includegraphics[width=1\textwidth]{../resources/diagram/M2Tdiagram}
\caption{The build system workflow} \label{fig:buildsystemworkflow}
\end{figure}
Orthogonal variabilityl\cite{Czarnecki-2012-Comparison} is the approach of documenting variability in SPL by separating the mapping of variability from the artifacts. KBuild seems to be a partially orthogonal solution by means of the specific syntax and separation into Makefiles with different filenames, however KBuild still uses the makefile syntax and is integrated into the artifacts of the build system and this is opposite to the objectives of orthogonal variability. Achieving an orthogonal way of mapping features to code is desirable because separating the mapping from artifacts can make the software easier to maintain. 

There are several embedded open source projects that use Kconfig\cite{berger-2012-variability} e.g. Coreboot\footnote{http://www.coreboot.org}, uClibc\footnote{ http://www.uclibc.org} and Busybox\footnote{http://www.busybox.net}.% where the Kconfig tool is included as separate source files. 

\section{Analysis \label{sec:ana}}
% Write domain analysis here.

It has been proven feasible to extract presence conditions from the Linux kernel\cite{Berger-2010-Mapping} using a tool called KBuildMiner.  We also found a methodology for extracting the coarse-grained variability called KBuildProbe \cite{Dietrich-2012-Extraction}. Since we were working within a limited scope on  a prototype that should demonstrate feasibility we chose to use a manual extraction technique similar to KBuildProbe. This existing research convinced us that we would be more likely to succeed if we used the projects that used KBuild as the main target of analysis. We found a couple projects that use KBuild, Coreboot and Busybox. 




%We presume this is because the KBuild syntax is short and concise and mostly used for mapping features to source code files.

Coreboot is an embedded project  that aims to replace the proprietary BIOS on motherboards. 
Busybox is another embedded project that makes many Unix tools available in several POSIX environments. Both Coreboot and Busybox use optional features and loose coupling but apparently not tristate.

In KBuild projects there is usually one filename that is used for the KBuild mapping across all directories with source code in them which is included in the root makefile. In Coreboots case this filename is \texttt{Makefile.in} and for Busybox it is\texttt{Kbuild.src} and they are included by the Makefile in the root folder. 
This way of separating mappings from the regular makefiles makes it easier to analyze and extract the mappings.

%We discovered several different kinds of variability mapping in the domain of open source software projects that we analyzed.

 
%One kind is the optional file compilation where the inclusion of files for the compilation of modules is based on conditional expressions evaluating a feature configuration. This is a popular topic for research of variability mapping and there is a (a condition for the inclusion of a specific artifact based on the evaluation of a feature).

The mapping of features to code based on the evaluation of a single boolean configuration variable being true can be expressed in two ways using the Makefile syntax:
\begin{verbatim}
ramstage-$(CONFIG_PCI) += pci_ops.c
ifeq ($(CONFIG_PCI_ROM_RUN),y)
ramstage-y += pci_rom.c
endif
\end{verbatim}
Sometimes these conditions are combined as seen in \texttt{Coreboot/src/lib/Makefile.in}
\begin{verbatim}
# The CBMEM implementations are chosen based on CONFIG_DYNAMIC_CBMEM.
ifeq ($(CONFIG_DYNAMIC_CBMEM),y)
ramstage-y += dynamic_cbmem.c
romstage-y += dynamic_cbmem.c
else
ramstage-y += cbmem.c
romstage-$(CONFIG_HAVE_ACPI_RESUME) += cbmem.c
endif # CONFIG_DYNAMIC_CBMEM
\end{verbatim}

The presence conditions for \texttt{dynamic\_cbmem.c} are simple enough for both \texttt{ramstage} and \texttt{romstage}
\begin{verbatim}
dynamic_cbmem.c : (CONFIG_DYNAMIC_CBMEM="y")
\end{verbatim}
The presence condition for the \texttt{ramstage} list for the \texttt{cbmem.c} is simply the inverse:
\begin{verbatim}
cbmem.c : !(CONFIG_DYNAMIC_CBMEM="y")
\end{verbatim}
However the presence condition for \texttt{romstage} is a little more complex:
\begin{verbatim}
cbmem.c : (CONFIG_HAVE_ACPI_RESUME="y")&& !(CONFIG_DYNAMIC_CBMEM="y")
\end{verbatim}

Presence conditions are not enough to recreate the mapping so we should also store the list that the mapping targets.

\section{Technical Solution \label{sec:tech}}
%The main difference between the original build system and the product of our DSL is that we generate a single Makefile responsible for building all source files  as opposite to a  system of Makefiles located in each subdirectory and responsible only for their local files.
%In contrast, the makefile generated by our DSL is monolithic and includes the inclusion conditions for all source files in the project.


We chose to support optional inclusion of files in modules for compilation because this is easy to extract, model and replace/evaluate compared to other kinds of variability. It seems like this is the type of mapping that could benefit the most from abstraction due to the sheer volume of this kind of mappings compared to the other kinds.
% due to the boolean nature of the features.



\subsection{Architecture}

%Two options: realization or pattern description


\begin{figure}[h!]
\centering
\includegraphics[width=0.8\textwidth]{../resources/diagram/MetamodelHierarchy}
\caption{The metamodel hierarchy} \label{fig:metamodelhierarchy}
\end{figure}

We created an abstract syntax by modeling the feature to code mapping meta-model using the ecore meta-meta-model. We implement the concrete syntax for the feature to code mapping DSL using Xtext and generate a text editor for our abstract syntax using the Model-Driven Development tools. 

We describe the mapping of a project e.g. Coreboot in our own DSL which we have abbreviated to  \texttt{ftc} as seen in the M1 layer of the metamodel hierarchy in Fig. \ref{fig:metamodelhierarchy}. In order to generate a Makefile from the instance of our concrete syntax we design a M2T template. This makefile will be compatible with an actual project which provides variability based on configuration.

\subsection{DSL}
In order to map features to artifacts there were two options of realizing the DSL editor. One option was to design a graphical DSL editor with features on one side and artifacts on the other and let the user draw lines between to express the mapping. The other option was to design a textual DSL editor which we chose to develop because it was easier to prototype, had greater granularity and our target users would be developers who we presume are already comfortable editing text and learning new textual syntaxes.

Our first challenge in modeling a textual DSL were filesystem paths. Filesystem paths allow dashes and periods e.g. \texttt{busybox/console-tools/loadkmap.o} and we couldn’t represent this as a simple string due to the nature of Xtext (underscores are excluded from special characters). Since we have focused exclusively on GNU make that runs on Linux we adopt the rules for paths from Linux by only supporting forward slashes that are used as path separators for directories. However we don’t support erroneous paths that start with special characters or that have more than one special character appearing in a row e.g..

We identified the problem as a well known way to model expressions as a tree \cite{Voelter-2010-dslbook}. In what is just a sequence of strings modeled as a tree the the \texttt{PathExpression} class seen in Fig. \ref{fig:FCMetaModel} includes a prefix on the left side and a suffix on the right side is called suffix while storing the separator as an enumerator.

There is a special technique to expressing the tree in the Xtext syntax as seen in the following example.

\begin{lstlisting}
PathExpression returns Path:
	Path ({PathExpression.prefix=current} 
special=PathEnum suffix=PathExpression)?;
\end{lstlisting}



We needed to provide a reference for all the lists/modules as well as the mandatory files to add to these modules for compilation. However not all modules have mandatory files so the this is optional as seen in the following example.
\begin{lstlisting}
Module:
	name=ID 
	('[' files+=PathExpression (files+=PathExpression)* ']')?;
\end{lstlisting}
\begin{figure}[h!]
  \centering
    \includegraphics[width=1\textwidth]{../resources/diagram/FeatureCodeMetaModel}
  \caption{The DSL metamodel} \label{fig:FCMetaModel}
\end{figure}


Another challenge was modeling the presence conditions. We chose to use simplified presence conditions that we call feature expressions. They can express any presence conditions where the presence of one or several features are evaluated with the following simple operators. 
\begin{lstlisting}
enum OperatorsEnum:
	NOT='!' | AND='&&' | OR='||';
\end{lstlisting}

The expressions are modeled using the strategy for modeling binary expressions as a tree. The presence conditions are simplified which means that we don’t support parantheses and this means that any unary expression e.g. with a \texttt{NOT} operator will be below a binary expression e.g. AND  in the parse tree.
\begin{lstlisting}
BinaryFeatureExpression returns FeatureExpression:
	(UnaryFeatureExpression | Feature) 
({BinaryFeatureExpression.left=current}
 operator=OperatorsEnum right=BinaryFeatureExpression)?;

UnaryFeatureExpression:
	operator=OperatorsEnum expr=Feature;
\end{lstlisting}


%The hierarchy of expressions is built so unary expressions cannot contain binary expressions so that unary expressions are always evaluated after binary expressions.

We also chose to exclude the support for tristate data type in presence conditions because we didn’t discover any tristate features in the makefiles of the projects that we target for support.% we analyzed that impacted file inclusion. 
% we can safely ignore the dynamic module part of the kbuild syntax when we build our makefile generator. 

%This made  it necessary for us to do complex modeling to express in our DSL by modeling unary and binary expressions with operators.


%- give the abstract syntax, meta model and examples of our concrete syntax




The following is an example of the resulting concrete syntax of our textual DSL. It starts with the name of the mapping. Afterwards modules are defined and their mandatory source files are listed. 
\begin{lstlisting}
Mapping device {
  ramstage [ device.c root_device.c ]
  romstage [ device_romstage.c ]
}
\end{lstlisting}
%In order to map features to code we write s. They bear the resemblance of traditional expressions in Java or other programming languages. 
For each feature expression we provide a list of optional files to compile if the feature evaluates to true. In the list of files of the second feature expression in the following example there are several files in subdirectories and we support that as well.
\begin{lstlisting}
!CONFIG_PCI_ROM_RUN && CONFIG_VGA_ROM_RUN:
  ramstage += pci_rom.c;

CONFIG_PCI_OPTION_ROM_RUN_YABEL:
  ramstage += oprom/x86emu/debug.c
		  oprom/x86emu/decode.c;
\end{lstlisting}


\subsection{Makefile generation}

We use an Xpand template along with a Modeling Workflow Engine 2 (MWE2) workflow to generate a monolithic Makefile from any inputs written in our DSL. The resulting Makefile can be built by the root Makefile of the project using a simple include statement. The statement should be placed after the inclusion of the .config file and should also precede any target definitions. The developer must know beforehand the name of the Makefile that is to be created. If the name is \texttt{Makefile.inc}, then:
\begin{verbatim}
include config/.config
include Makefile.inc
all: real-all
\end{verbatim}

One challenge was to translate the feature expressions into the Makefile syntax. Note that the following examples use the XPand template syntax and some new lines have been inserted to keep the lines contained in the document.

In order to translate a \texttt{BinaryFeatureExpression} to makefile syntax we use the shell function, which is an advanced feature of the Makefile language. The feature expressions are passed to and evaluated by an instance of the shell process. 
\begin{verbatim}
«DEFINE mappingcont_condition FOR BinaryFeatureExpression»
ifeq ($(shell [[ «EXPAND expression FOR this» ]] && echo true )
,true)
«ENDDEFINE»
\end{verbatim}

The expression of the \texttt{BinaryFeatureExpression} class might take on three different forms and we define three expansions for this containment.
\begin{verbatim}
«DEFINE expression FOR BinaryFeatureExpression»
«EXPAND expression FOR left» «operator» 
«EXPAND expression FOR right»«ENDDEFINE»
«DEFINE expression FOR UnaryFeatureExpression»«operator»
«EXPAND expression FOR expr»«ENDDEFINE»
«DEFINE expression FOR Feature»$(«name») == "y"«ENDDEFINE»
\end{verbatim}
Using this the Makefile generator will pick the expansion depending on which subclass of \texttt{FeatureExpression} the expression implements.
An example of the output of the template follows.
\begin{verbatim}
ifeq ($(shell [[ $(CONFIG_PCI_ROM_RUN) == "y" 
|| $(CONFIG_VGA_ROM_RUN) == "y" ]] && echo true ),true)
\end{verbatim}
%ifeq ($(shell [[ !$(CONFIG_RELOCATABLE_MODULES) == "y" 
%&& $(CONFIG_RELOCATABLE_RAMSTAGE) == "y" ]] && echo true ),true)



\section{Evaluation \label{sec:eval}}
In this section we evaluate the feasibility of using the DSL prototype for the objectives defined previously. 

We chose to analyze and reengineer parts of the build system of the open source project Coreboot and Busybox by translating parts of it to our DSL. 

In Coreboot the number of Makefiles that are included by KBuild in the source folder is 371. 
However only a small number of the makefiles use coarse-grained variability of the type that we have described. The reason we use Coreboot for evaluation is that a few Makefiles have mappings with some complex presence conditions that we can use to test the feasibility of our DSL. 

Busybox mostly has simple presence conditions using KBuild syntax. In Busybox the number of KBuild related makefiles is 34.  We assume that it is possible to extract and model at least approximately 85\% of the makefiles. However due to our small group size we found little time to evaluate this project completely.
% using our DSL however due to limits on group members we only managed to model approximately 9%.

Coreboot and the six Makefiles located in \texttt{./src/device} and its subdirectories describe the mapping of features to code. We extract the presence conditions manually with the associated modules. In general the extraction is quite simple if it is done straight from KBuild syntax. However sometimes there are more complicated conditions. 
The following block from \\\texttt{Coreboot/src/device/Makefile.inc}
\begin{verbatim}
ifeq ($(CONFIG_PCI_ROM_RUN),y)
ramstage-y += pci_rom.c
else
ramstage-$(CONFIG_VGA_ROM_RUN) += pci_rom.c
endif
\end{verbatim}
can be translated into our DSL as:
\begin{lstlisting}
CONFIG_PCI_ROM_RUN||CONFIG_VGA_ROM_RUN:
  ramstage += pci_rom.c;
\end{lstlisting}

As a benefit the feature expression shortens the conditional statement to one instead of two as well as providing a more simple and readable syntax. The developer using the build system won’t need to learn and use the conditional statements and syntax constraints of Makefiles. They can use simple Boolean expressions instead. 


The Coreboot project consists of three key stages - bootblock, romstage and ramstage. They provide different functionality and therefore they are compiled into independent binaries from different source files.  In the Coreboot makefiles the stages are described as lists of source files. Different stages need different commands to compile them e.g. ramstage requires special compilation to be run in memory compared to romstage.
To demonstrate the multiple modules of Coreboot an example loosely based on \texttt{Coreboot/src/lib/Makefile.inc} follows.
For the bootblock stage the following optional inclusion of source files is described:
\begin{verbatim}
ifneq ($(CONFIG_HAVE_ARCH_MEMSET),y)
bootblock-y += memset.c
endif
\end{verbatim}
For the ramstage and romstage there are mandatory and optional files:
\begin{verbatim}
ramstage-y += coreboot_table.c
ramstage-y += hardwaremain.c
ramstage-y += selfboot.c
ifneq ($(CONFIG_HAVE_ARCH_MEMSET),y)
ramstage-y += memset.c
endif

romstage-y += memchr.c
ifneq ($(CONFIG_HAVE_ARCH_MEMCPY),y)
romstage-y += memcpy.c
endif
\end{verbatim}
%\newpage
In our DSL the stages of Coreboot are simply represented as modules:
\begin{lstlisting}
Modules {
  ramstage 
    [ coreboot_table.c hardwaremain.c selfboot.c ]
  romstage
    [ memchr.c ]
  bootblock
}
!CONFIG_HAVE_ARCH_MEMSET
  bootblock += memset.c
  ramstage += memset.c
!CONFIG_HAVE_ARCH_MEMCPY
  romstage += memcpy.c
\end{lstlisting}
By translating the Makefiles to our DSL we have proved that it is feasible to model multiple collections of artifacts for compilation with our DSL. These could be binaries, libraries or modules part of a single project that share common source files and variation rules.

Busybox has some mappings that rely on the same presence conditions across directories and they can be joined together into one mapping as seen in the following example. Since the mappings of a variability feature are all in the same place they can easily be removed if the feature is removed.
\begin{lstlisting}
CONFIG_TAR:
  lib += archival/tar.o archival/libarchive/get_header_tar.o;
\end{lstlisting}

Some of the mappings in Busybox use loose coupling which it is also possible to model with our DSL. As an example see this line from \\\texttt{Busybox/coreutils/Kbuild.src}.
\begin{verbatim}
libs-y += libcoreutils/
\end{verbatim}
All the source code files contained in the directory \texttt{libcoreutils} are part of the mandatory mapping to the module \texttt{libs} and can be expressed in our DSL.
\begin{lstlisting}
libs
[ coreutils/libcoreutils ]
\end{lstlisting}
%One of the major pros of our DSL is that when removing a feature you can just remove the mapping block directly without having to search several directories and files.

%Busybox is a project that uses kbuild for makefile building. Creating manual mappings for subdirectories was extra work but we came to the conclusion that we should be able to model the kbuild mappings of busybox.

If you use the regular KBuild style of structuring your build system in projects with Makefiles in each folder it might make it difficult to get an overview of how the variability configuration affects the compilation process. Addition, removal or renaming of a single variability feature requires changes in multiple files. By using the developed DSL all the mappings are located in one file. Basic evolutionary changes to the variability like renaming or removing features or mappings can all be performed on a single file.

Creating an instance of the shell process can incur a performance penalty when the control flow will evaluate the mappings. However we found that this is the most feasible way to express the control flows that use complex presence conditions and the performance difference should be neglible.

Overall it is feasible to express the control flow for the mapping of features to files in Makefiles using our DSL. 
Moreover the DSL is as concise as possible while keeping some of the familiar syntax of Makefiles in order to make it easy for users to migrate any existing mappings from Kbuild/Makefile syntax to our DSL.
% The scope of this external DSL is narrow to encourage adoption and reusability.

%One alternative could be to reverse the mapping by mapping features to files.
%\subsection{Correctness}


\section{Threats to Validity \label{sec:threats}}
%\subsection{Internal validity}
In order to evaluate our DSL we reengineered the existing KBuild mappings of features to code manually from the existing software projects. This required manual searching and editing of many makefiles across a mature software project. Any manual process can be prone to human error and this is a major threat to the validity of our evaluation. We mitigated this threat by only evaluating the complex mappings that we could find to minimize the role that human error could play.
%A way to mitigate the threat of manual extraction would be to adapt an existing extractor/miner for presence conditions like KBuildminer\cite{Berger-2010-Mapping} to our needs of storing the target module for the mapping. 

Our evaluation is threatened by the performance of the changes that a generated makefile would impair compared to the original makefile.
%A threat to the validity could be that we do not measure if there are any performance differences when using a generated makefile compared to the original makefile. 
If the performance is worse this might threaten the adoption of the DSL because the drawbacks are too large compared with the benefits.

% We could have additionally specified the percentage of the project that we would be able to model with our DSL.

%Internal threats: manual extraction of PCs
%External: less useful solution for developers, no user study (only inside group) which could be valuable for future work

Another threat was whether the DSL would be useful for developers in the sense that it would save time and effort. In order to determine the usefulness of the DSL we evaluated it internally within our group as developers. A better way of evaluating the usefulness could be to do a user study of developers that would attempt the adoption of the DSL for their software project. Afterwards the developers could be questioned whether they would draw benefit from using our DSL for embedded projects.

%Most projects that use Kconfig have very little in common regarding their makefile structure. 
%This might be an external threat to the validity because the DSL will in all likelihood need project specific customization to be compatible with other projects than Coreboot. 

%\subsection{External validity}
%We only evaluated approximately 3\% of coreboot’s total lines of makefiles dedicated to mapping features to code.


%Busybox is strictly kbuild mappings structured in files.

%Evaluate how much of the project makefiles we can represent. External threat to validity could be lack of relevance of our metamodel if there are too few projects which accommodate variability in configuration.


%\section{Discussion}
%- state that we are designing our dsl on the go as a prototype we iterate on
%Mapping model Development Process

%If all software projects had orthogonal variability and were designed proactively to model mapping of features to artifacts it would make it relatively easy to maintain a software product line. However many vital software projects aren’t designed recently and sometimes use mature tools without any support for further abstraction. Several workarounds exist such as using the directory structure for abstraction.


% and being proactive approach of modeling variability using an abstraction standard like Common Variability Language (CVL)\cite{Czarnecki-2012-Comparison} it would remove the need for extracting and creating mappings based on kbuild and Makefiles.



%Presence conditions (PC) are represented by our DSL as the Boolean expressions. The process between is straightforward. In a makefile, the developer should use a limited set of conditional statements (ifeq, ifneq, ifdef, ifndef) and nest them to achieve the three basic operations in the boolean algebra. This process is slow and as the complexity of the expressions increases, the result becomes error prone and overly complicated.
%It is clear that we can express the feature to code mapping more concisely by using our DSL compared to the makefile syntax.


\section{Related Work \label{sec:related}}
%-- how is this related to our work?
%The topic of mapping features to code in build systems has been researched in the last couple of years and several tools have been built for extraction.
%\subsection{Dynamic}
A new standard\footnote{http://www.omgwiki.org/variability/doku.php} called Common Variability Language (CVL) encompasses the domain from modeling variability to mapping it to artifacts in a structured manner.
One of the main benefits of CVL is that it is domain independent\cite{Czarnecki-2012-Comparison} and it makes it possible to define variability mapping outside of the artifacts (like makefiles or source  code). In future software projects it can be a solution to achieving orthogonality in the variability mappings for build systems.
With our contribution we have shown it is feasible to extract the mappings and express the mappings and this creates the possibility of reengineering existing projects to use CVL.
%However there is probably little benefit in migrating a project to CVL retroactively so it has little relevance to the existing open source projects that we analyzed.

A different proactive framework that has been built to map features to artifacts is the EMF based plugin FeatureMapper\footnote{http://featuremapper.org/} for the IDE Eclipse. It supports manual and automatic mapping of features to any EMF model artifact e.g. classes in a class diagram. After designing a feature configuration a developer can transform UML diagrams that the features map to into new models that only include specific artifacts that the specific feature configuration maps to. 
%This is irrelevant to the existing software projects, that we found because none of them were designed using EMF models that were supported by the build system. 
We have shown that it is feasible to extract mappings from features to files in a textual editor. FeatureMapper is a visual tool and new embedded software projects might draw benefit from using modeling in their design phase to keep track of mapping from features to artifacts.

Passos et al.\cite{passos2012towards} analyze the evolution in developer commits to the Version Control System for the Linux kernel in regards to the variability mapping of three spaces: configuration space (intended variability), compilation space (coarse-grained variability) and implementation space (fine-grained variability). They identify four different recurring patterns of evolution that affect the variability e.g. removing a feature as optional in order to incorporate it as a mandatory part of the software. This is relevant because the research contributes to the understanding of the evolution of the coarse-grained variability of the Linux kernel and we assume there are similar patterns in the embedded projects that we analyzed. Our contribution can help externalize the mappings to make it easier to track the changes in the evolution of variability.


%Realization of variability is also part of source code in C projects [Sincero-2010-Algorithm]  and Sincero, Tartler and Lohmann show that it is feasible to extract mapping of features retroactively using their algorithm.

%As the software engineering community has discovered the benefits of Software Product Line as a concept several projects proactively realize variability. 

%Several technical software tools exist that can nearly realize the concepts of feature and decision models e.g. KConfig for C projects in Linux or the Component Description Language (CDL) in the eCos operating system \cite{Berger-2010-Variability}. CDL is similar to Kconfig but adds functions and operations that support arithmetics and strings. They can be evaluated later on by the build system outside of the models.

%The analysis and extraction of fine-grained variability mapping has been researched as well\cite{Sincero-2010-Algorithm}. Sincero, Tartler and Lohmann show that it is feasible to extract mapping of features from code retroactively using their own algorithm designed for the purpose. They face some of the same challenges that we have faced like nested conditions just in different artifacts that are source code files and not build tool files.

%Schaefer et al.\cite{Schaefer-2010-DOP} analyze the methodology for developing software product lines and they design a new delta oriented programming language that will allow inclusion and exclusion of code in software projects based on the features selected in a specific software product line. This is relevant because it illustrates the feasibility in taking a proactive approach to the evolution of features in a software product line. It is a valuable result that can be used to manifest the importance of  documenting variability proactively.


%Mbeddr uses special notation in C source code to apply variability based on feature selection.









%- Cite papers about CVL
\section{Conclusion \label{sec:conc}}
In this paper we have demonstrated the feasibility of describing mapping between features and code in a textual DSL developed using Model-driven development tools. We iteratively developed an abstract syntax based on our understanding of build systems from open source projects that we analyzed. Furthermore we implemented the concrete syntax for the feature to code mapping DSL, and we evaluated our language by reengineering a subset of makefiles from an open source embedded project. Using these mappings we could generate a monolithic makefile to replace the mappings in the existing project.
%The generated makefile resembles an actual makefile of a project which provides variability based on configurations. 

We have reached our objective by proving the feasibility of designing a DSL that can express the mapping of coarse-grained variability in embedded software projects that use KBuild in a simple way that helps avoid redundancies in mappings. This is useful for developers who maintain software product lines because it can improve the traceability in the evolution of variability.

We hope that our work will contribute to increasing awareness of achieving an orthogonal level of variability in software projects.
% by encouraging the ongoing work of reengineering projects that use kbuild. 
Our prototype might not be able to support the reengineering of a couple of software projects that use KBuild but we can argue that our metamodel is mostly domain independent, and it might inspire future projects to use an orthogonal approach to mapping coarse-grained variability.

%For future work it could be useful to extend the KBuildMiner to extract mapping into a DSL.
\newpage
\bibliographystyle{splncs}
\bibliography{references}
\end{document}